package sortedcollection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import be.kuleuven.cs.som.annotate.Basic;

/**
 * A collection that is always been sorted by the natural ordering of the given element.
 * 
 * @invar The elements will be sorted ascending all the time (the biggest at the end).
 * 		| hasProperElements()
 * 
 * @author Molderez Tom, 2de bach Ingenieurswetenschappen Computerwetenschappen-Elektrotechniek and Reniers Jorn, 2de bach Ingenieurswetenschappen Werktuigkunde-Computerwetenschappen
 * @version 2.0
 *
 * @param <E> A class implementing the Comparable interface.
 */
public class SortedCollection<E extends Comparable<? super E>> implements Collection<E> {
	
	private final List<E> list = new ArrayList<E>();
	
	/**
	 * Creates a new empty SortedCollection.
	 * 
	 * @post The sortedCollection will not contain any element.
	 * 		| (new this).isEmpty() == true
	 */
	public SortedCollection() {
	}
	
	/**
	 * Checks if this list is ordered ascending (the biggest at the end).
	 * 
	 * @return True if the list contains no objects at all.	
	 * 		| if this.isEmpty()
	 * 		|	result == true
	 * @return True when the list is ordered ascending, otherwise false.
	 * 		| let ordered = true
	 * 		| for each index in {1,2,..,this.size()-1}
	 * 		|	if this.get(index - 1).compareTo(this.get(index)) > 0
	 * 		|	  then ordered = false
	 * 		| result == ordered 
	 */
	public boolean hasProperElements() {
		for(int index = 1; index < this.size(); index ++)
			if(list.get(index - 1).compareTo(list.get(index)) > 0)
				return false;
		return true;
	}
	
	/**
	 * Adds an element to the SortedCollection at the position to respect the sort definition.
	 * 
	 * The time complexity for adding an element is log(n). The position is calculated
	 * using binary search.
	 * 
	 * @param element The element to be added.
	 * @post The element will be added to the list.
	 * 		| (this new).contains(element)
	 * @post The size will be incremented.
	 * 		| (new this).size() == this.size() ++
	 */
	@Override
	public boolean add(E element) {
		if(this.isEmpty())
			list.add(element);
		else {
			int index = Collections.binarySearch(list, element); 
			if(index < 0) // if the item isn't yet in the list, binarySeach returns the index where it should be
				index = - index -1;// and in order to let this know, it returns a negative number.
			list.add(index, element);
		}
		return true;
	}
	
	/**
	 * This method adds all the elements in the given collection to this. The complexity is m*log(m)*n,
	 * with n the amount of elements to add, m the total amounts in the sortedCollection after adding.
	 * 
	 * @param collection A collection with elements of the same class as this.
	 * @post This will contain all the elements of the collection.
	 * 		| for each element in {collection}
	 * 		|	(this new).contains(element)
	 * @post The size will be increased with the size of collection.
	 * 		| (new this).size() == this.size() + collection.size()
	 * @throws ClassCastException
	 * 		If the list contains elements that are not mutually comparable (for example, strings and integers)
	 * 		or if the class of an element of the specified collection prevents it from being added to this collection.
	 * 		| !(new this).hasProperExelements()
	 * @throws NullPointerException
	 * 		If collection is null.
	 * 		| collection == null
	 */
	@Override
	public boolean addAll(Collection<? extends E> collection) throws ClassCastException, NullPointerException {
		list.addAll(collection);
		Collections.sort(list);
		return true;
	}

	/**
	 * Returns the element at the given index. 
	 * 
	 * @throws IndexOutOfBoundsException
	 * 		When the index is not legal.
	 * 		| index < 0 || index >= this.size()
	 */
	@Basic
	public E get(int index) throws IndexOutOfBoundsException {
		return list.get(index);
	}
	
	/**
	 * Returns an iterator over the elements in this list in proper sequence.
	 * 
	 * @return
	 * 		| let temp be an empty ArrayList
	 * 		| for each i in {0, 1, ..., this.size()-1}
	 * 		|	temp.add(this.get(i))
	 * 		| result == temp.iterator()
	 */
	@Override
	public Iterator<E> iterator() {
		return list.iterator();
	}

	/**
	 * Returns the number of elements in this list. 
	 */
	@Basic @Override
	public int size() {
		return list.size();
	}

	/**
	 * Removes all of the elements from this list. The list will be empty after this call returns. 
	 * 
	 * @post
	 * 		| this.size() == 0
	 */
	@Override
	public void clear() {
		list.clear();
	}

	/**
	 * Returns true if this list contains the specified element.
	 * 
	 * @return
	 * 		| let flag is false
	 * 		| for each object in {get(0), get(1), ..., get(size()-1)}
	 * 		|	if (o == null && object == null || object.equals(o)
	 * 		|		then flag is true
	 * 		| result == flag
	 */
	@Override
	public boolean contains(Object o) throws ClassCastException, NullPointerException {
		return list.contains(o);
	}

	/**
	 * Returns true if this list contains all of the elements of the specified collection. 
	 * 
	 * @return
	 * 		| let flag is true
	 * 		| for each object in {c}
	 * 		|	if !this.contains(object)
	 * 		|		then flag is false
	 * 		| result == flag
	 * @throws ClassCastException
	 * 		if the types of one or more elements in the specified collection are incompatible with this list.
	 * 		| let flag is false
	 * 		| for each object in {c}
	 * 		|	if !E.class.isInstance(c)
	 * 		|		then flag is true
	 * 		| flag
	 * @throws NullPointer
	 * 		If the specified collection is null.
	 * 		| c == null
	 */
	@Override
	public boolean containsAll(Collection<?> c) throws ClassCastException, NullPointerException {
		return list.containsAll(c);
	}

	/**
	 * Returns whether this list is empty.
	 * 
	 * @return 
	 * 		| result == (this.size() == 0)
	 */
	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}

	/**
	 * Removes the first occurrence of the specified element from this list, if it is present.
	 * 
	 * @post
	 * 		| let temp be an empty ArrayList
	 * 		| for each i in {0, 1, ..., this.size()-1}
	 * 		|	temp.add(this.get(i))
	 * 		| temp.remove(o)
	 * 		| (new this) == temp
	 */
	@Override
	public boolean remove(Object o) {
		return list.remove(o);
	}

	/**
	 * Removes from this list all of its elements that are contained in the specified collection.
	 * 
	 * @effect
	 * 		| for each object in {c}
	 * 		|	this.remove(object)
	 */
	@Override
	public boolean removeAll(Collection<?> c) throws ClassCastException, NullPointerException {
		return list.removeAll(c);
	}
	
	/**
	 * Retains only the elements in this list that are contained in the specified collection. 
	 * In other words, removes from this list all the elements that are not contained in the specified collection. 
	 * 
	 * @post
	 * 		| let temp be an empty ArrayList
	 * 		| for each i in {0, 1, ..., this.size()-1}
	 * 		|	temp.add(this.get(i))
	 * 		| temp.retainAll()
	 * 		| (new this) == temp
	 */
	@Override
	public boolean retainAll(Collection<?> c) throws ClassCastException, NullPointerException {
		return list.retainAll(c);
	}

	/**
	 * Returns an array containing all of the elements in this list in proper sequence (from first to last element). 
	 * 
	 * @post
	 * 		| let temp be an empty ArrayList
	 * 		| for each i in {0, 1, ..., this.size()-1}
	 * 		|	temp.add(this.get(i))
	 * 		| result == temp.toArray()
	 */
	@Override
	public Object[] toArray() {
		return list.toArray();
	}

	/**
	 * Returns an array containing all of the elements in this list in proper sequence (from first to last element);
	 *  the runtime type of the returned array is that of the specified array. 
	 *  If the list fits in the specified array, it is returned therein. 
	 *  Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.
	 *  If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), 
	 *  the element in the array immediately following the end of the collection is set to null. 
	 *  (This is useful in determining the length of the list only if the caller knows that the list does not contain any null elements.) 
	 *  
	 *  @post
	 * 		| let temp be an empty ArrayList
	 * 		| for each i in {0, 1, ..., this.size()-1}
	 * 		|	temp.add(this.get(i))
	 * 		| result == temp.toArray(a)
	 * @throws NullPointerException
	 * 		If the specified array is null.
	 * 		| a == null
	 * @throws ArrayStoreException
	 * 		If the runtime type of the specified array is not a supertype of the runtime type of every element in this list.
	 * 		| let flag is false
	 * 		| for each object in {get(0), get(1),..., get(size()-1)}
	 * 		|	if !T.class.isInstance(object)
	 * 		|		then flag is true
	 * 		| flag
	 */
	@Override
	public <T> T[] toArray(T[] a) throws NullPointerException, ArrayStoreException {
		return list.toArray(a);
	}

}
